class BSTIterator {
public:
    stack<TreeNode*> st;
    TreeNode* cur;
                                        
    BSTIterator(TreeNode* root) {
        cur = root;
    }
                                       
    int next() {
        while(cur){
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        int ret = cur->val;
        cur = cur->right;
        
        return ret;
    }
    
    bool hasNext() {
        return !st.empty() || cur;
    }
};
